The present invention relates to an input buffering switch for use in a packet switching system, more particularly to a virtual output queuing (VOQ) in the input buffering switch.
In a recent packet switching system, so as to realize a high-speed and high-capacity switch, sometimes is employed an input buffering switch having N kinds of input and N kinds of output (N is a natural number, hereinafter, likewise), and yet having N virtual output queuing (VOQ).
FIG. 9 is a block diagram illustrating a configuration of a conventional input buffering type packet switch using the virtual output queuing (VOQ).
As shown in the same drawing, a packet switch 100 comprises first to N-th input interface sections 101-1 to 101-N that input data, first to N-th output interface sections 102-1 to 102-N that output data, a data switching element 103 that makes switching for data input from the input interface sections 101-1 to 101-N to transfer it to the output interface sections 102-1 to 102-N, and a switch scheduler 104 that controls the data switching element 103.
Each of the first to the N-th input interface sections 101-1 to 101-N comprises a destination address resolution and forwarding engine section (FE) 105, a packet assembly and disassembly section (PAD) 106, and a virtual output queuing (VOQ) 107.
The destination address resolution and forwarding engine section 105 makes solution for a destination of a packet sent from a transmission line and a class to which it belongs.
The packet assembly and disassembly section (PAD) 106 splits the packet into cells with a fixed size. In this packet switch 100, a bandwidth of the transmission line and the switch within a device is managed by cell unit.
Assume that the class number, which is handled in the packet switching system, is K, the virtual output queuing (VOQ) 107 has K×N kinds of output, and logical queues that corresponded to each class. Each cell disassembled in the packet assembly and disassembly section (PAD) 106 is stored in a buffer within the virtual output queuing (VOQ) 107 responding to the destination or the class.
The data switching element 103 is configured of N×N cross point switches.
Based on information obtained from the first to N-th input interface sections 101-1 to 101-N, the switch scheduler 104 meditates cell transfer request of these first to N-th input interface sections 101-1 to 101-N, and gives cell transfer permission to respective virtual output queuings (VOQS) 107.
Also, the switch scheduler 104 was adapted so that, by controlling the data switching element 103, the cells output from the virtual output queuing (VOQ) 107 are switched over to the corresponding destination out of the output interface sections 102-1 to 102-N.
At this moment, C cells (C is a natural number) are transferred within the switch as one unit. C is a fixed value that is decided responding to a system. In this specification, this one unit's cell is referred to as a super cell.
Each of the first to N-th output interface sections 102-1 to 102-N was configured of a virtual input queue (VIQ) 108 and a packet assembly section (PAD) 109.
The virtual input queue (VIQ) 108 also includes KN kinds of output, and logical queues that corresponded to each class.
The super cells sent from the data switching element 103 are stored in the virtual input queue (VIQ) 108, which corresponds to a input interface number and a class number of a sending end, out of the virtual input queues (VIQs) 108 within the first to N-th output interface sections 102-1 to 102-N, and are returned to an original packet by the packet assembly section (PAD) 109.
Hereinafter, the packets are output to the transmission line.
FIG. 10 is a block diagram illustrating a configuration of the virtual output queuing (VOQ) 107.
The virtual output queuing (VOQ) 107 comprises a VOQ buffer 120 and a VOQ controlling section 130.
The VOQ buffer 120 comprises first to N-th buffers by output ports 121-1 to 121-N. Assume that the class number, which is handled in the packet switching system, is K, the first to N-th buffers by output ports 121-1 to 121-N have logical queues that corresponded to the K classes.
The VOQ controlling section 130 was configured of a destination information allocation section 131 and first to N-th VOQ controlling sections by output ports 132-1 to 132-N.
Based on destination/class information 133 that is notified from the destination address resolution and forwarding engine section (FE) 105, the VOQ controlling section 130 takes write control for a cell 125 that is sent from the packet assembly and disassembly section (PAD) 106.
Also, the VOQ controlling section 130 issues to the switch scheduler 104 connection request 136 of the data switching element 103 for switching the super cell, and further receives connection permission 137 that results from the connection request meditated in the switch scheduler 104 to control the read-out of the cell and the transfer of the super cell to the data switching element 103.
Based on the destination/class information 133 that is notified from the destination address resolution and forwarding engine section (FE) 105, the destination information allocation section 131 generates cell write controlling information 134, notifies it to the first to N-th buffers by output ports 121-1 to 121-N, and takes write control for the cell 125 that is sent from the packet assembly and disassembly section (PAD) 106.
Based on the destination/class information 133, the destination information allocation section 131 notifies class information 135 to the VOQ controlling section by output ports 132-j (j=1, 2, 3, - - - , n) of the corresponding destination.
The first to N-th VOQ controlling sections by output ports 132-1 to 132-N manage the received class information 135, generate the connection request 136 to notify it to the switch scheduler 104, simultaneously receive the connection permission 137 that results from the connection request meditated in the switch scheduler 104, generate cell read-out controlling information 138, and notify it to the first to N-th buffers by output ports 121-1 to 121-N.
According to the cell write controlling information 134 sent from the destination information allocation section 131, the first to N-th buffers by output ports 121-1 to 121-N accumulate the cells 125 that are sent from the packet assembly and disassembly section (PAD) 106.
Also, the first to N-th buffers by output ports 121-1 to 121-N read out the cells based on the cell read-out controlling information 138, and constructs super cells 126, and sends them to the data switching element 103.
The virtual input queue (VIQ) 108 also has a similar configuration to that of the virtual output queuing (VOQ) 107. The virtual input queue (VIQ) 108 has logical queues of each sending end/class instead of each destination/class in the virtual output queuing (VOQ) 107.
The packet switch 100 quantizes operating time within an interface with the cell taken as the unit. This quantization unit is referred to as a time slot. The transfer within a crossbar switch is carried out with the super cell consisting of C cells. A switching period at this moment operates C times of the time slot.
In the recent packet switching system, is often used a switch with N kinds of input and N kinds of output like the input buffering packet switch 100 as shown in FIG. 9. Further, so as to transfer packet traffics having different traffic requirement conditions (a delay guarantee, a bandwidth guarantee, and a best effort) within the switch according to these conditions, the class is defined by traffic requirement conditions, and priority control is often taken among the classes.
For this end, a VOQ controlling function of meditating the cell transfer request that is issued from each logical queue to generate the connection request to the data switching element 103, and the switch scheduler 104, which meditates the connection request to the data switching element 103 to take control of the connection of cross point switches, become necessary.
In particular, in the event that the usage bandwidth is guaranteed as the class unit and that the free bandwidth exists within the transmission line and the device, realization of a service for utilizing the free bandwidth fairly among classes, which hope to utilize it, has been required. This service is referred to as a minimum bandwidth guarantee-type service. Realization of a VOQ controlling function with which this service is realized has been requested.
A conventional example of the VOQ controlling section by output ports 132 having the VOQ controlling function with which such a minimum bandwidth guarantee-type service was realized is illustrated in FIG. 11.
The VOQ controlling section by output ports 132 is configured of a class information allocation section 141, first to K-th class bandwidth management sections 142-1 to 142-K, a connection request generation section 143, and a super cell read-out controlling section 144.
Each of the first to K-th class bandwidth management sections 142-1 to 142-K was configured of a bandwidth conformance determination unit 145, a conforming cell counter 146, and a non-conforming cell counter 147.
The connection request generation section 143 was configured of a total conforming cell number counter 148 and a total no-conforming cell number counter 149.
In the class information allocation section 141, the class information 135 of each class sent from the destination address resolution and forwarding engine section (FE) 105 is allocated to one certain class bandwidth management section 142-j (J=1, 2, 3, - - - , k) that is decided by this information.
Based on the received class information 135, the first to K-th class bandwidth management sections 142-1 to 142-K determine conformance or non-conformance for each cell by the bandwidth conformance determination unit 145.
Also, the first to K-th class bandwidth management sections 142-1 to 142-K measure the conforming cell number Vijk and the non-conforming cell number Wijk in the conforming cell counter 146 and the non-conforming cell counter 147.
In the bandwidth conformance determination unit 145 are managed a remaining credit Cijk of a guarantee bandwidth portion, a credit Zijk that is given time slot by time slot, and a time tijk that the destination/class, which corresponded to the previous time, arrived.
The bandwidth conformance determination unit 145 determines conformance or non-conformance of the cell responding to size of the remaining credit Cijk.
In the connection request generation section 143, the total conforming cell number counter 148 and the total non-conforming cell number counter 149 measure the total conforming cell number Vij and the total non-conforming cell number Wij sent from each class.
The connection request generation section 143 generates the connection request 136 to the switch scheduler 104 from the total conforming cell number Vij and the total non-conforming cell number Wij sent from each class. The generation interval of the connection request 136 becomes each C time slot.
When the super cell read-out controlling section 144 received the connection permission 137 from the switch scheduler 104, it decides which cells are to be read out based on the status of the conforming cell counter 146 and the non-conforming cell counter 147 of each class, and notifies them as the cell read-out controlling information 138 to the VOQ buffer 120.
Hereinafter, an operation of the conventional input buffering packet switch 100 shown in FIG. 9, FIG. 10, and FIG. 11 will be explained, referring to flowcharts.
At first, a connection request generation operation at the moment of arrival of the cell will be explained.
FIG. 12 is a flowchart illustrating operations time slot by time slot of the destination information allocation section 131 at the moment of arrival of the information by classes shown in FIG. 10, the class information allocation section 141 shown in FIG. 11, the first to K-th class bandwidth management sections 142-1 to 142-K, and the connection request generation section 143.
Hereinafter, an operation at the moment of having received the information by destinations/classes of each cell will be explained, referring to FIG. 12.
When the information by destinations/classes 133 is received (step A1), a destination (j) and a class (K) are decided in the destination information allocation section 131 and the class information allocation section 141 (step A2).
In the class bandwidth management section 142-j (J=1, 2, 3, - - - , k) of the selected destination/class is updated the remaining credit Cijk (step A3).
Herein, in the event that the remaining credit Cijk is one or more (Cijk≧1) (YES at step A4), the cell is determined to be “conforming” to perform addition of the conforming cell counter 146, subtraction of a credit counter, and addition of the total conforming cell number counter 148 (step A5).
In this stage, in the event that the total conforming cell number count value (Vij) is C or more (YES at step A6), the connection request 136 with priority 1 is notified to the switch scheduler 104 (step A7), and the operation is finished by subtracting only C, which is an already-notified portion, from the total conforming cell number count value (Vij)(step A8).
In the event that the total conforming cell number count value (Vij) is below C (NO at step A6), the operation is finished without executing the subsequent processes, that is, the steps A7 and A8.
On the other hand, in the event that the remaining credit Cijk is below one (Cijk<1) (NO at step A4), the cell is determined to be “non-conforming” to perform addition of the non-conforming cell counter 147, and addition of the total non-conforming cell number counter 149 (step A9).
In this stage, in the event that the total non-conforming cell number count value (Wij) is C or more (YES at step A10), the connection request 136 with priority 2 is notified to the switch scheduler 104 (step A11), and only C, which is an already-notified portion, is subtracted from the total non-conforming cell number count value (Wij)(step A12).
In the event that the total non-conforming cell number count value (Wij) is below C (NO at step A10), the operation is finished without executing the subsequent processes, that is, the steps A11 and A12.
Next, a QoS (Quality of Service) class selection operation for constructing the super cell for transfer at the moment of receiving the connection permission will be explained.
FIG. 13 is a flowchart illustrating an operation of the super cell read-out controlling section 144.
Hereinafter, an operation at the moment of receiving the connection permission will be explained, referring to FIG. 13.
When the connection permission is received (step D1), the number n of a send cell selection process is taken as 0 (zero)(step D2). In the event that the number n of the send cell selection process is below C (n<C)(YES at step D3), the send cell selection process is activated one time (step D4), one is added to n (step D5), and watch and wait are kept for one cell time (step D6).
At the moment that the send cell selection process was activated C times (NO at step D3), the operation of the super cell read-out controlling section 144 finishes.
The order in the send cell selection process is (1) selection from the conforming cell side, and (2) selection from the non-conforming cell side.
In the event that the conforming cell was counted in any class (when anyone of 1≧k≧K conforming cell counters Vijk is 0 (zero) or more ) (YES at step E1), the class is selected from the classes (Vijk>0), in which the conforming cell exists, by means of the round robin algorithm (step E2).
One is subtracted from the conforming cell count of the selected class (step E3).
In the event that the conforming cell was not counted in any class (NO at step E1), it is determined whether or not the non-conforming cell was counted in any class (step E4).
In the event that the non-conforming cell was counted in any class (when anyone of 1≧k≧K non-conforming cell counters Wijk is 0 (zero) or more ) (YES at step E4), the class is selected from the classes (Wijk>0), in which the non-conforming cell exists, by means of the round robin algorithm (step E5).
One is subtracted from the non-conforming cell count of the selected class (step E6).
In the event that the non-conforming cell was not counted in any class (NO at step E4), the cells to be read out do not exist, whereby it is notified that the cells to be read out do not exist (step E7).
In the event of employing the VOQ management technique explained above to configure the input buffering packet switch using the virtual output queuing (VOQ), a function necessary for the switch scheduler 104 is to reply to the VOQ controlling section 130 with the connection permission (information quantity: N) between the input port and the output port from the connection request with a two-stage priority (information quantity: 2*N2) between the input port and the output port.
Information of the QoS class is unnecessary for connection request information. This is because priority information was decided from the traffics of each QoS class in the VOQ controlling section 130.
Information of the priority is unnecessary for connection permission information. This is because selection was made of the cells of the QoS class to be transferred to the data switching element 103 in the VOQ controlling section 130 side.
The QoS support method of this technique is a method of having a class based queuing (CBQ) as a basis, however it differs in a certain important point from the class based queuing (CBQ).
This is the point that this packet switch, which is arranged within a network, runs a conformance check on each traffic class.
This packet switch realized a guarantee of the bandwidth with what is refereed to as “a credit”. The cell having the credit is refereed to as a “conforming” cell, and the cell not having the credit is refereed to as a “non-conforming” cell. Schematically, the traffic, which did not use the assigned bandwidth up, results in being mentioned as “conformance”.
The important point of this technique is that the non-conforming traffic is not abandwidthoned simply but is allowed to pass as long as it does not compete with the conforming traffic.
Also, the characteristic point is the point that a plurality (K kinds) of the classes are handled in the input interface/output interface side, whereas two kinds of priority information are notified to the switch scheduler side. If the switch scheduler 104 can take priority control with two priorities, it is enough. Even though the class number (K), which is handled in this packet switching system, is increased, a complexity degree of the switch scheduler 104 does not change.
In accordance with the conventional packet switch described above, the “minimum bandwidth guarantee-type service”, in which the minimum bandwidth is guaranteed and the free bandwidth is fairly utilized among the classes that hope to utilize it, can be realized.
In the conventional packet switch described above, however, it is impossible to simultaneously realize a CBR (Constant Bit Rate) service, which is required to simultaneously guarantee the bandwidth and the delay, and the minimum bandwidth guarantee-type service. There are two points as to the reason. The first reason is because of competition among the input interfaces, and second reason is because of competition among classes within the input interface. Hereinafter, these two reasons will be explained.
The first reason is that, even though the CBR traffic was assigned to a certain class, and the connection request with a high priority was sent to the switch scheduler, there is the possibility that it might be blocked by the connection request with a high priority of the traffic of the class of the minimum bandwidth guarantee-type service, which is input from the other input interface. The switch scheduler can view only two kinds of priorities, high/low, whereby it is impossible to make such discriminating assignment that is advantageous to the CBR traffic.
The second reason originates in the fact that the readout control is taken by means of the round robin algorithm among the classes within the input interface. For this end, it is impossible to make such discriminating assignment that is advantageous to the CBR traffic.